﻿// 1363. 形成三的最大倍数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;
/*
https://leetcode.cn/problems/largest-multiple-of-three/

给你一个整数数组 digits，你可以通过按 任意顺序 连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。
由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。如果无法得到答案，请返回一个空字符串。返回的结果不应包含不必要的前导零。



示例 1：
输入：digits = [8,1,9]
输出："981"

示例 2：
输入：digits = [8,6,7,1,0]
输出："8760"

示例 3：
输入：digits = [1]
输出：""

示例 4：
输入：digits = [0,0,0,0,0,0]
输出："0"


提示：
1 <= digits.length <= 10^4
0 <= digits[i] <= 9
*/



class Solution {
public:
    bool solve(vector<int>& digits) {
        int sum = 0;
        for (int i = 0; i < digits.size(); i++) {
            sum += digits[i];
        }
        if (sum % 3 == 0) return true;
       
        int need = sum % 3;
        sort(digits.begin(), digits.end());
        vector<int> arr1;  vector<int> arr2;
        for (int i = 0; i < digits.size(); i++) {
            if (digits[i] % 3 == 1) { arr1.push_back(digits[i]); }
            if (digits[i] % 3 == 2) { arr2.push_back(digits[i]); }
        }
        
        if (need == 1 && arr1.size() > 0) {
            digits.erase(lower_bound(digits.begin(), digits.end(), arr1[0]));
            return true;
        }
        else if (need == 2 && arr2.size() > 0) {
            digits.erase(lower_bound(digits.begin(), digits.end(), arr2[0]));
            return true;
        }
        else if (need == 1 && arr2.size() > 1) {
            digits.erase(lower_bound(digits.begin(), digits.end(), arr2[0]));
            digits.erase(lower_bound(digits.begin(), digits.end(), arr2[1]));
            return true;
        }
        else if (need == 2 && arr1.size() > 1) {
            digits.erase(lower_bound(digits.begin(), digits.end(), arr1[0]));
            digits.erase(lower_bound(digits.begin(), digits.end(), arr1[1]));
            return true;
        }

        return false;
    }

    string largestMultipleOfThree(vector<int>& digits) {
        string ans;
        
        if (solve(digits) == false) {
            return ans;
        }

        sort(digits.begin(), digits.end(), greater<int>());

        for (int i = 0; i < digits.size(); i++) {
            ans += ('0' + digits[i]);
        }
        if (ans.size() > 1 && ans[0] == '0' && ans[1] == '0') ans = "0";
        return ans;
    }
};

int main()
{
    Solution s;
    vector<int> v{ 8,6,7,1,0 };
    s.largestMultipleOfThree(v);
}

 